package com.li.algorithm.leetcode.hot100;

import java.util.ArrayList;
import java.util.List;

public class Test19 {
    /**
     * 方法1：按层遍历
     *   时间复杂度：O(mn)
     *   空间复杂度：O(1)
     */
//    public List<Integer> spiralOrder(int[][] matrix) {
//        //行数
//        int row = matrix.length-1;
//        //列数
//        int col = matrix[0].length-1;
//        int start = 0;
//        int circle = (Math.min(row+1, col +1) + 2 -1) / 2;
//        ArrayList<Integer> result = new ArrayList<>();
//        while (circle > 0) {
//            //[0][0] - [0][n-1]
//            for (int j = start; j <= col; j++) {
//                result.add(matrix[start][j]);
//            }
//            //[1][n-1] - [n-1][n-1]
//            for (int i = start+1; i <= row; i++) {
//                result.add(matrix[i][col]);
//            }
//            //[n-1][n-1] - [n-1][0]
//            for (int j = col-1; j >= start && row > start; j--) {
//                result.add(matrix[row][j]);
//            }
//            //[n-1][0] - [1][0]
//            for (int i = row-1; i >= start+1 && start < col; i--) {
//                result.add(matrix[i][start]);
//            }
//            circle--;
//            start++;
//            row--;
//            col--;
//        }
//        return result;
//    }

    /**
     * 方法2：模拟路径
     *   时间复杂度：O(mn)
     *   空间复杂度：O(mn)
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        //visited标记是否被访问过
        //路径的长度即为矩阵中的元素数量
        ArrayList<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return result;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int total = row * col;
        int x = 0, y = 0;
        boolean[][] vis = new boolean[row][col];
        //按照旋转路径的顺序排序
        int[][] direction = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        //控制方向：0-右，1-下，2-左，3-上
        int directionIndex = 0;
        for (int i = 0; i < total; i++) {
            result.add(matrix[x][y]);
            vis[x][y] = true;
            //试探下一个位置是否可以前进
            int nextX = x + direction[directionIndex][0];
            int nextY = y + direction[directionIndex][1];
            //转向
            if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col || vis[nextX][nextY]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            //进入转向后的位置
            x += direction[directionIndex][0];
            y += direction[directionIndex][1];
        }
        return result;
    }

    public static void main(String[] args) {
        List<Integer> result = new Test19().spiralOrder(new int[][]{
                {1,2,3},
                {4,5,6},
                {7,8,9}
        });
        System.out.println(result);
    }
}
